#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void subsetsWithDupHelper(vector<int> &S, int index, vector<vector<int> > &ans, vector<int> &cur)
{
    ans.push_back(cur);

    if (index == S.size()) return;
    
    for (int i = index; i < S.size(); i++) {
	if (i != index && S[i] == S[i-1]) continue;
	cur.push_back(S[i]);
	subsetsWithDupHelper(S, i+1, ans, cur);
	cur.pop_back();
    }
}


vector<vector<int> > subsetsWithDup(vector<int> &S) {
    vector<vector<int> > ans;
    vector<int> cur;
    sort(S.begin(), S.end());
    subsetsWithDupHelper(S, 0, ans, cur);      
    return ans;
}

int main(int argc, char **argv)
{
    vector<int> input;
    int a[] = {1,2,2,2};
    for (int i = 0; i < sizeof(a)/sizeof(int); i++)
	input.push_back(a[i]);
   
    vector<vector<int> > ans = subsetsWithDup(input);
    
    for (int i = 0; i < ans.size(); i++) {
	for (int j = 0; j < ans[i].size(); j++) {
	    cout << ans[i][j] << " ";
	}
	cout << endl;
    }
}
